package logica;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BuscaEmProfundidade {

	private Arvore arvore;
	private Vertice objetivo;
	private ArrayList<Vertice> visitados = new ArrayList<Vertice>();
	private boolean encontrou;

	public ArrayList<Vertice> getVisitados() {
		return visitados;
	}

	private Stack <Vertice> pilha = new Stack<>();

	public Stack<Vertice> getPilha() {
		return pilha;
	}

	public BuscaEmProfundidade(Arvore arvore, Vertice objetivo) {
		this.arvore = arvore;
		this.objetivo = objetivo;
	}

	public boolean buscar(Vertice origem) {
		//Adiciona o vertice origem e seus adjacentes a lista de vertices arvore
		arvore.adicionaVertice(origem);
		arvore.getAdjacentes(origem, true);
		Vertice[] vertices = arvore.getVerticesIniciais();

		for (Vertice v : vertices) {
			if (encontrou)
				return encontrou;
			pilha.push(v);
			encontrou = v.equals(objetivo);
			if ((!encontrou) && (!v.foiVisitado())) {
				visitar(v);
			} else {
				return encontrou;
			}
		}
		return encontrou;
	}

	public boolean visitar(Vertice vert) {
		vert.setVisitado(true);
		visitados.add(vert);

		List<Vertice> adjacentesDoVertice = arvore.getAdjacentes(vert, true);
		for (Vertice adj : adjacentesDoVertice) {
			if (encontrou)
				return true;
			else
				encontrou = adj.equals(objetivo);
			if (encontrou){
				visitados.add(adj);
				pilha.push(adj);
				return true;
			}

			if  (!adj.foiVisitado()) {
				pilha.push(adj);
				visitar(adj);
			}
		}
		if (!encontrou) {
			pilha.pop();
		}

		return encontrou;
	}
}
